In most computations, sorting of data is a dominant procedure. It has been estimated that virtually every important aspect of programming includes sorting and searching. In database applications, sorting is one of the main operations. Computer manufacturers have estimated that a significant percent of the run time of a computer is spent in sorting.
Accordingly, numerous hardware sorting algorithms have been proposed to increase speed of sorting. Particular attention has recently been directed to the new VLSI (very large scale integration) technology for sorting applications. VLSI technology permits a large number of devices to fit on a single chip. Algorithms which provide high throughput are necessary to take advantage of the VLSI technology as it relates to sorting.
A number of papers have been written describing algorithms based on systolic arrays, including:
Carey, M. J. Hansen, P. M., and Thompson, C. D., "RESST: A VLSI Implementation of a Record Sorting Stack," Tech. Report UCB/CSD 82/102, Computer Science Division, Univ. of California, Berkeley (April, 1979). PA1 Kung, H. T., "Why Systolic Architectures?" Computer Magazine Vol. 15(1), pp. 37-46 (January 1982). PA1 Leiserson, C. E., "Systolic Priority Queues," Tech. Report CMU-CS-79-115, CMU Computer Science Department (April, 1979). PA1 Song, S. W., "On a High-Performance VLSI Solution to Database Problems," Tech. Report CMU-CS-81-142, CMU Computer Science Department (August, 1981). PA1 Watanabe, I., "VLSI Implementation of Odd-Even PA1 Sorter Using a Uniform Ladder," Tech. Report Tr 85, Department of Computer Science, Univ. of Rechester (November, 1981). PA1 Chen, T. C., Eswaran, K. P., Lum, V. Y., and Tung, C., "Simplified Odd-Even Sort Using Multiple Shift-Register Loops," International Journal of Computer and Information Science Vol. 17(3) (1978). PA1 Winslow, L. E. and Chow, Y., "The Analysis and Design of Some New Sorting Machines," IEEE TRANSACTIONS ON COMPUTERS Vol. C-32(7), pp. 667-683 (July, 1983) PA1 q is the number of leaves on the merge tree; PA1 V=mq.sup.p is the number of data items to be sorted; and PA1 p is the number of external buffer memory modules
Carey et al discloses a VLSI implementation of a record sorting stack which is essentially a linear array version of the classic bubble sort algorithm. Leiserson discloses a systolic priority queue which is a sorter based on bubble sort. Song discloses a systolic tree device and shows that the tree device disclosed therein and Leiserson's priority queue can perform sorting in optimum time. Watanabe, on the other hand, discloses a systolic VLSI implementation of odd-even sorter, a type of bitonic sorting network, using the uniform ladder such as proposed by Chen et al in
However, it is understood that bitonic sorting algorithms have better average computing speed, but are more complicated to be implemented in hardware, and almost impossible to be independent of the problem size.
The VLSI sort arrays discussed above all require O(V)* time to sort, where V is the number of items to be sorted. However, these devices require at least O(V) array cells so that when V is large, such devices are impractical, particularly since V varies from problem to problem. Breaking large sets of items into smaller sets and sorting each of the smaller sets by a sorting device of size S to be merged by multi-way sort increases the practicability but also increases the time complexity to ##EQU1## which may be too large when V is very large compared to S. FNT *O(V) means order of V.
A measure of efficiency for comparing different parallel sorters has been suggested in
based on the input or the output being sequential or parallel. Their efficiency measure, however, does not take into account the complexity of the basic sorting element and the time required to perform each of the atomic steps.
Accordingly, it is an object of the present invention to provide a sorting array which utilizes a minimum of cells and which is both practicable and flexible. It is also an object of the present invention to provide a sorting array which can provide relational database operations by the addition of pre- and post filters because sorting is a dominant operation in database operations.